Introduction

This vignette illustrates the use of INLA for spatial prediction using examples from Blangiardo and Cameletti (2015) and Illian, Sørbye, and Rue (2012). For prediction of continuous spatial processes, the stochastic partial differential equations (SPDE) approach is used to approximate the process through an areal Gaussian Markov random field (GMRF) representation.

GMRF Background

Blangiardo and Cameletti (2015) section 6.1.

SPDE Background

Find Lindgren et. al. (2011) and fill in motivation

Geostatistics Example

Toy dataset from Blangiardo and Cameletti (2015).

# Plot the data.
plot(s2 ~ s1, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0), data = SPDEtoy, pch = 19, asp = 1, main = 'Toy Data')

# Create a mesh for the SPDE method and then plot it.
toy_mesh <- inla.mesh.2d(as.matrix(SPDEtoy[,c('s1', 's2')]), max.edge = c(0.1, 0.2))
plot(toy_mesh, asp = 1)
points(SPDEtoy$s1, SPDEtoy$s2, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0, 0.5), pch = 20)

# SPDE projector matrix for estimation.
A_est <- inla.spde.make.A(toy_mesh, as.matrix(SPDEtoy[,c('s1', 's2')]))

# Initialize exponential covariance structure for SPDE.
spde <- inla.spde2.matern(mesh = toy_mesh, alpha = 2)

# Set up stack for estimation.
stack_index <- inla.spde.make.index(name = 'spatial_field', n.spde = spde$n.spde)
stack_est <- inla.stack(data = list(y = SPDEtoy$y), A = list(A_est), effects = list(c(stack_index, list(intercept = 1))), tag = 'est')

# Create a grid for prediction.
toy_nx <- 50
toy_ny <- 50
toy_grid <- expand.grid(x = seq(0, 1, length.out = toy_nx), y = seq(0, 1, length.out = toy_ny))

# SPDE projector matrix for prediction.
A_pred <- inla.spde.make.A(mesh = toy_mesh, loc = as.matrix(toy_grid))

# Set up stacks for prediction.
stack_latent <- inla.stack(data = list(xi = NA), A = list(A_pred), effects = list(stack_index), tag = 'pred_latent')
stack_response <- inla.stack(data = list(y = NA), A = list(A_pred), effects = list(c(stack_index, list(intercept = 1))), tag = 'pred_response')

# Join all three stacks.
stacks <- inla.stack(stack_est, stack_latent, stack_response)

# Fit the model with INLA.
toy_fit <- inla(
  y ~ -1 + intercept + f(spatial_field, model = spde),
  data = inla.stack.data(stacks),
  control.predictor = list(A = inla.stack.A(stacks), compute = TRUE)
)

# Output posterior summaries.
toy_fit$summary.fixed
toy_fit$summary.hyperpar
# Extract posterior mean of latent spatial field.
index_latent <- inla.stack.index(stacks, tag = 'pred_latent')$data
post_mean <- toy_fit$summary.linear.predictor[index_latent, 'mean']
post_sd <- toy_fit$summary.linear.predictor[index_latent, 'sd']

# Plot the posterior mean and SD of the latent spatial field.
plot(im(matrix(post_mean, nrow = toy_nx, ncol = toy_ny), xrange = range(toy_grid$x), yrange = range(toy_grid$y)), main = 'Posterior Mean of Spatial Field')
points(SPDEtoy$s1, SPDEtoy$s2, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0, 0.5), pch = 20)

plot(im(matrix(post_sd, nrow = toy_nx, ncol = toy_ny), xrange = range(toy_grid$x), yrange = range(toy_grid$y)), main = 'Posterior SD of Spatial Field')
points(SPDEtoy$s1, SPDEtoy$s2, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0, 0.5), pch = 20)

Bei Dataset and inlabru

Example from Møller and Waagepetersen (2007), Beilschmiedia pendula Lauraceae locations in a plot in Panama. bei dataset in spatstat (Baddeley and Turner 2005).

# Plot the full point pattern.
plot(bei, pch = '.', cols = 'black', main = 'Realized Point Pattern')

bei_corners <- vertices.owin(Window(bei))
bei_domain <- cbind(bei_corners$x, bei_corners$y)
bei_full_mesh <- inla.mesh.2d(cbind(bei$x, bei$y),
                              cutoff = 50, max.edge = c(50, 100),
                              loc.domain = bei_domain)
plot(bei_full_mesh, asp = 1)
plot(Window(bei), border = 'blue', add = TRUE)
points(bei, pch = '.', col = 'blue')

bei_full_spdf <- as.SpatialPoints.ppp(bei)
# CHECK PRIORS!
matern_full <- inla.spde2.pcmatern(bei_full_mesh,
                                   prior.sigma = c(0.1, 0.99),
                                   prior.range = c(5, 0.01))
cmp_full <- coordinates ~ mySmooth(map = coordinates, model = matern_full) + Intercept
bei_full_lgcp <- lgcp(cmp_full, bei_full_spdf)
lambda_full <- predict(bei_full_lgcp, pixels(bei_full_mesh), ~ exp(mySmooth + Intercept))

# Plot posterior means and posterior sd.
plot(lambda_full)
plot(Window(bei), border = 'white', add = TRUE)
points(bei, pch = '.', col = 'white')

plot(lambda_full['sd'])
plot(Window(bei), border = 'white', add = TRUE)
points(bei, pch = '.', col = 'white')

# Take a sample of quadrats and plot the observed point pattern.
set.seed(84323)
n_quads <- 10
botleft <- cbind(runif(n_quads, 0, 950), runif(n_quads, 0, 450))
bei_interior <- lapply(seq_len(nrow(botleft)), function(r){return(
    cbind(
      botleft[r, 1] + c(0, 0, 50, 50),
      botleft[r, 2] + c(0, 50, 50, 0)
    )
  )})
bei_win <- do.call(
  union.owin,
  apply(botleft, 1, function(x){return(
    owin(x[1] + c(0, 50), x[2] + c(0, 50))
  )})
)
bei_hole <- bei[complement.owin(bei_win)]
bei_samp <- bei[bei_win]
bei_window_full <- Window(bei)

plot(bei_hole, main = 'Observed Subregion', pch = '.', cols = 'black')

bei_hole_mesh <- inla.mesh.2d(cbind(bei_hole$x, bei_hole$y),
                              cutoff = 50, max.edge = c(50, 100),
                              loc.domain = bei_domain)
plot(bei_hole_mesh, asp = 1)
plot(Window(bei), border = 'blue', add = TRUE)
points(bei_hole, pch = '.', col = 'blue')

bei_hole_spdf <- as.SpatialPoints.ppp(bei_hole)
# CHECK PRIORS!
matern_hole <- inla.spde2.pcmatern(bei_hole_mesh,
                                   prior.sigma = c(0.1, 0.99),
                                   prior.range = c(5, 0.01))
cmp_hole <- coordinates ~ mySmooth(map = coordinates, model = matern_hole) + Intercept
bei_hole_lgcp <- lgcp(cmp_hole, bei_hole_spdf)
lambda_hole <- predict(bei_hole_lgcp, pixels(bei_hole_mesh), ~ exp(mySmooth + Intercept))

# Plot posterior means and posterior sd.
plot(lambda_hole)
plot(Window(bei_hole), border = 'white', add = TRUE)
points(bei_hole, pch = '.', col = 'white')

plot(lambda_hole['sd'])
plot(Window(bei_hole), border = 'white', add = TRUE)
points(bei_hole, pch = '.', col = 'white')

plot(bei_window_full, main = 'Observed Sample')
plot(bei_win, add = TRUE)
plot(bei_samp, pch = '.', cols = 'black', add = TRUE)

bei_samp_mesh <- inla.mesh.2d(cbind(bei_samp$x, bei_samp$y),
                              cutoff = 50, max.edge = c(50, 100),
                              loc.domain = bei_domain)
plot(bei_samp_mesh, asp = 1)
plot(Window(bei), border = 'blue', add = TRUE)
plot(Window(bei_samp), border = 'blue', add = TRUE)
points(bei_samp, pch = '.', col = 'blue')

bei_samp_spdf <- as.SpatialPoints.ppp(bei_samp)
# CHECK PRIORS!
matern_samp <- inla.spde2.pcmatern(bei_samp_mesh,
                                   prior.sigma = c(0.1, 0.99),
                                   prior.range = c(5, 0.01))
cmp_samp <- coordinates ~ mySmooth(map = coordinates, model = matern_samp) + Intercept
bei_samp_lgcp <- lgcp(cmp_samp, bei_samp_spdf)
lambda_samp <- predict(bei_samp_lgcp, pixels(bei_samp_mesh), ~ exp(mySmooth + Intercept))

# Plot posterior means and posterior sd.
plot(lambda_samp)
plot(Window(bei), border = 'white', add = TRUE)
plot(Window(bei_samp), border = 'white', add = TRUE)
points(bei_samp, pch = '.', col = 'white')

plot(lambda_samp['sd'])
plot(Window(bei), border = 'white', add = TRUE)
plot(Window(bei_samp), border = 'white', add = TRUE)
points(bei_samp, pch = '.', col = 'white')

Bei Dataset without inlabru

centers <- gridcenters(dilation(bei_window_full, 40), 40, 20)
dx <- sum(unique(centers$x)[1:2] * c(-1, 1)) / 2
dy <- sum(unique(centers$y)[1:2] * c(-1, 1)) / 2
bei_df <- data.frame(x = centers$x, y = centers$y,
                     count = NA_integer_, area = NA_real_)

for(r in seq_len(nrow(bei_df))){
  bei_df$count[r] <- sum(bei$x >= bei_df$x[r] - dx &
                         bei$x < bei_df$x[r] + dx &
                         bei$y >= bei_df$y[r] - dy &
                         bei$y < bei_df$y[r] + dy)
  bei_df$area[r] <- area(Window(bei)[owin(c(bei_df$x[r] - dx, bei_df$x[r] + dx), c(bei_df$y[r] - dy, bei_df$y[r] + dy))])
}

par(mar = c(0.5, 0, 2, 2))
plot(im(t(matrix(bei_df$count, nrow = length(unique(bei_df$x)))), unique(bei_df$x), unique(bei_df$y), unitname = 'meters'), ncolcours = range(bei_df$count) %*% c(-1, 1) + 1, main = 'Binned Tree Counts')
plot(bei_window_full, border = 'white', add = TRUE)
points(bei, pch = '.', col = 'black')

# SPDE projector matrix for estimation.
full_A_est <- inla.spde.make.A(bei_full_mesh, as.matrix(bei_df[bei_df$area > 0, c('x', 'y')]))

# Initialize exponential covariance structure for SPDE.
full_spde <- inla.spde2.matern(mesh = bei_full_mesh, alpha = 2)

# Set up stack for estimation.
stack_index <- inla.spde.make.index(name = 'spatial_field', n.spde = full_spde$n.spde)
stack_est <- inla.stack(data = list(count = bei_df$count[bei_df$area > 0], larea = log(bei_df$area[bei_df$area > 0])), A = list(full_A_est), effects = list(c(stack_index, list(intercept = 1))), tag = 'est')

# SPDE projector matrix for prediction.
full_A_pred <- inla.spde.make.A(mesh = bei_full_mesh, loc = as.matrix(bei_df[,c('x', 'y')]))

# Set up stacks for prediction.
stack_latent <- inla.stack(data = list(xi = NA), A = list(full_A_pred), effects = list(stack_index), tag = 'pred_latent')
stack_response <- inla.stack(data = list(count = NA), A = list(full_A_pred), effects = list(c(stack_index, list(intercept = 1))), tag = 'pred_response')

# Join all three stacks.
stacks <- inla.stack(stack_est, stack_latent, stack_response)

# Fit the model with INLA.
bei_full_fit <- inla(
  count ~ -1 + intercept + f(spatial_field, model = full_spde),
  offset = larea, family = 'poisson',
  data = inla.stack.data(stacks),
  control.predictor = list(A = inla.stack.A(stacks), compute = TRUE)
)

# Output posterior summaries.
bei_full_fit$summary.fixed
bei_full_fit$summary.hyperpar
# Extract posterior mean of latent spatial field.
index_pred <- inla.stack.index(stacks, tag = 'pred_latent')$data
post_mean <- bei_full_fit$summary.linear.predictor[index_pred, 'mean']
post_sd <- bei_full_fit$summary.linear.predictor[index_pred, 'sd']

# Plot the posterior mean and SD of the latent spatial field.
plot(im(t(matrix(post_mean, nrow = length(unique(centers$x)), ncol = length(unique(centers$y)))), unique(centers$x), unique(centers$y)), main = 'Posterior Mean of Spatial Field')
plot(bei_window_full, add = TRUE)
points(bei, pch = '.', col = 'black')

plot(im(t(matrix(post_sd, nrow = length(unique(centers$x)), ncol = length(unique(centers$y)))), unique(centers$x), unique(centers$y)), main = 'Posterior SD of Spatial Field')
plot(bei_window_full, add = TRUE)
points(bei, pch = '.', col = 'black')

beihole_df <- data.frame(x = centers$x, y = centers$y,
                         count = NA_integer_, area = NA_real_)

for(r in seq_len(nrow(beihole_df))){
  beihole_df$count[r] <- sum(bei_hole$x >= beihole_df$x[r] - dx &
                             bei_hole$x < beihole_df$x[r] + dx &
                             bei_hole$y >= beihole_df$y[r] - dy &
                             bei_hole$y < beihole_df$y[r] + dy)
  beihole_df$area[r] <- area(Window(bei_hole)[owin(c(beihole_df$x[r] - dx, beihole_df$x[r] + dx), c(beihole_df$y[r] - dy, beihole_df$y[r] + dy))])
}

par(mar = c(0.5, 0, 2, 2))
plot(im(t(matrix(beihole_df$count, nrow = length(unique(beihole_df$x)))), unique(beihole_df$x), unique(beihole_df$y), unitname = 'meters'), ncolcours = range(beihole_df$count) %*% c(-1, 1) + 1, main = 'Binned Tree Counts')
plot(Window(bei_hole), border = 'white', add = TRUE)
points(bei, pch = '.', col = '#00000040')

References

Baddeley, Adrian, and Rolf Turner. 2005. “Spatstat: An R Package for Analyzing Spatial Point Patterns.” Journal of Statistical Software 12 (6): 1–42.

Blangiardo, Marta, and Michela Cameletti. 2015. Spatial and Spatio-Temporal Bayesian Models with R-INLA. Wiley.

Illian, Janine B, Sigrunn H Sørbye, and Håvard Rue. 2012. “A Toolbox for Fitting Complex Spatial Point Process Models Using Integrated Nested Laplace Approximation (Inla).” The Annals of Applied Statistics, 1499–1530.

Møller, J, and RP Waagepetersen. 2007. “Modern Spatial Point Process Modelling and Inference.” Scandinavian Journal of Statistics 34: 643–711.

LS0tCnRpdGxlOiAiU3BhdGlhbCBQcmVkaWN0aW9uIHdpdGggSU5MQSIKYXV0aG9yOiAiS2VubmV0aCBBLiBGbGFnZyIKYmlibGlvZ3JhcGh5OiAiLi4vcmVmZXJlbmNlcy5iaWIiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgZmlnX2hlaWdodDogNgogICAgZmlnX3dpZHRoOiAxMAogICAgZmlnX2Nyb3A6IEZBTFNFCiAgICBoZWlnaHQ6ICI5NjBweCIKICAgIHdpZHRoOiAiNzIwcHgiCiAgICBzZWxmX2NvbnRhaW5lZDogVFJVRQotLS0KCgpgYGB7ciBzZXR1cCwgY2FjaGUgPSBGQUxTRSwgZWNobyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGNhY2hlID0gRkFMU0UsIGVjaG8gPSBUUlVFLCB3YXJuaW5nID0gRkFMU0UsCiAgbWVzc2FnZSA9IEZBTFNFLCBkcGkgPSAxNTAsIGZpZy5hbGlnbiA9ICdjZW50ZXInKQpgYGAKCmBgYHtyIHBhY2thZ2VzLCBjYWNoZSA9IEZBTFNFLCBlY2hvID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFfQpsaWJyYXJ5KHNwYXRzdGF0KQpsaWJyYXJ5KElOTEEpCmxpYnJhcnkoaW5sYWJydSkKbGlicmFyeShtYXB0b29scykKYGBgCgoKIyBJbnRyb2R1Y3Rpb24KClRoaXMgdmlnbmV0dGUgaWxsdXN0cmF0ZXMgdGhlIHVzZSBvZiBJTkxBIGZvciBzcGF0aWFsIHByZWRpY3Rpb24gdXNpbmcgZXhhbXBsZXMKZnJvbSBAcmlubGEgYW5kIEBpbGxpYW5ldGFsLiBGb3IgcHJlZGljdGlvbiBvZiBjb250aW51b3VzIHNwYXRpYWwgcHJvY2Vzc2VzLAp0aGUgc3RvY2hhc3RpYyBwYXJ0aWFsIGRpZmZlcmVudGlhbCBlcXVhdGlvbnMgKFNQREUpIGFwcHJvYWNoIGlzIHVzZWQgdG8KYXBwcm94aW1hdGUgdGhlIHByb2Nlc3MgdGhyb3VnaCBhbiBhcmVhbCBHYXVzc2lhbiBNYXJrb3YgcmFuZG9tIGZpZWxkIChHTVJGKQpyZXByZXNlbnRhdGlvbi4KCgojIEdNUkYgQmFja2dyb3VuZAoKQHJpbmxhIHNlY3Rpb24gNi4xLgoKLSBPYnNlcnZhdGlvbnMgYWdncmVnYXRlZCB0byBkaXNqb2ludCBhcmVhbCByZWdpb25zIGluZGV4ZWQgYnkgJGkkLgotIEVhY2ggcmVnaW9uIGhhcyB1bmlxdWUgcGFyYW1ldGVyICRcdGhldGFfe2l9JC4KLSAkXG1hdGhjYWx7Tn0oaSkkIGlzIHRoZSBzZXQgb2YgaW5kaWNlcyBvZiBuZWlnaGJvcnMgb2YgcmVnaW9uICRpJCBhbmQKICAkXG1hdGhjYWx7Tn1fe2l9ID0gfFxtYXRoY2Fse059KGkpfCQgaXMgdGhlIG51bWJlciBvZiBuZWlnaGJvciBvZiByZWdpb24gJGkkLgotIExvY2FsIE1hcmtvdiBwcm9wZXJ0eTogZ2l2ZW4gJFxib2xkc3ltYm9se1x0aGV0YX1fe1xtYXRoY2Fse059KGkpfSQsCiAgJFx0aGV0YV97aX0kIGlzIGluZGVwZW5kZW50IG9mIGFsbCBvdGhlciAkXHRoZXRhX3tqfSQuCi0gVGhlbiB0aGUgcHJlY2lzaW9uIG1hdHJpeCAkXG1hdGhiZntRfSQgb2YgJFxib2xkc3ltYm9se1x0aGV0YX0kIGlzIHNwYXJzZQogIGJlY2F1c2Ugb25seSBuZWlnaGJvcnMgaGF2ZSBub256ZXJvIGNvcHJlY2lzaW9ucy4KCi0gQmVzYWctWW9yay1Nb2xsaSYjeDAwZTg7IG1vZGVsOgogICAgLSBFeGNoYW5nZWFibGUgcmFuZG9tIGVmZmVjdHMgJHVfe2l9JCB3aXRoIGludHJpbnNpYyBjb25kaXRpb25hbAogICAgICBhdXRvcmVncmVzc2l2ZSAoaUNBUikgc3RydWN0dXJlLgogICAgLSAkdV97aX18XG1hdGhiZnt1fV97LWl9IFxzaW0gXG1hdGhybXtOfVxsZWZ0KFxtdV97aX0gKyBcc3VtX3tqfSBhX3tpan0gKHVfe2p9IC0gXG11X3tqfSkgLyBcbWF0aGNhbHtOfV97aX0sIFxzaWdtYV97dX1eezJ9IC8gXG1hdGhjYWx7Tn1fe2l9XHJpZ2h0KSQKICAgIC0gKFdoYXQgYXJlIHRoZSAkYV97aWp9PyQpLgogICAgLSBpQ0FSIGlzIGFuIGltcHJvcGVyIHByaW9yIGJlY2F1c2UgY292YXJpYW5jZSBtYXRyaXggbm90IHBvc2l0aXZlIGRlZmluaXRlCiAgICAgIGJ1dCB0aGlzIGlzIG9rIGZvciByYW5kb20gZWZmZWN0cy4KCgojIFNQREUgQmFja2dyb3VuZAoKKkZpbmQgTGluZGdyZW4gZXQuIGFsLiAoMjAxMSkgYW5kIGZpbGwgaW4gbW90aXZhdGlvbioKCi0gU3BhdGlhbCBwcm9jZXNzICRceGkoXG1hdGhiZntzfSkkLgoKLSBTb2x2ZSAkKFxrYXBwYV57Mn0gLSBcRGVsdGEpXntcYWxwaGEgLyAyfShcdGF1IFx4aShcbWF0aGJme3N9KSkgPSBcbWF0aGNhbHtXfShcbWF0aGJme3N9KSQuCiAgICAtICRca2FwcGEkIGlzIGEgcmFuZ2UgcGFyYW1ldGVyLgogICAgLSAkXERlbHRhJCBpcyB0aGUgTGFwbGFjaWFuLgogICAgLSAkXGFscGhhJCBpcyBhIHNtb290aG5lc3MgcGFyYW1ldGVyLgogICAgLSAkXHRhdSQgYSBwcmVjaXNpb24gcGFyYW1ldGVyLgogICAgLSBFeGFjdCBhbmQgc2F0aW9uYXJ5IHNvbHV0aW9uOiAkXHhpKFxtYXRoYmZ7c30pJCBpcyBhIEdhdXNzaWFuIGZpZWxkIHdpdGggTWF0JiN4MDBlODtybiBjb3ZhcmlhbmNlIGZ1bmN0aW9uLgoKLSBGaW5pdGUgZWxlbWVudCBhcHByb3hpbWF0aW9uICQkLgoKCiMgR2Vvc3RhdGlzdGljcyBFeGFtcGxlCgpUb3kgZGF0YXNldCBmcm9tIEByaW5sYS4KCmBgYHtyIHNwZGV0b3ksIGZpZy53aWR0aCA9IDYsIG91dC53aWR0aCA9ICc2MCUnfQojIFBsb3QgdGhlIGRhdGEuCnBsb3QoczIgfiBzMSwgY29sID0gcmdiKFNQREV0b3kkeSAvIG1heChTUERFdG95JHkpLCAwLCAwKSwgZGF0YSA9IFNQREV0b3ksIHBjaCA9IDE5LCBhc3AgPSAxLCBtYWluID0gJ1RveSBEYXRhJykKYGBgCgpgYGB7ciBzcGRlbWVzaCwgZmlnLndpZHRoID0gNiwgb3V0LndpZHRoID0gJzYwJSd9CiMgQ3JlYXRlIGEgbWVzaCBmb3IgdGhlIFNQREUgbWV0aG9kIGFuZCB0aGVuIHBsb3QgaXQuCnRveV9tZXNoIDwtIGlubGEubWVzaC4yZChhcy5tYXRyaXgoU1BERXRveVssYygnczEnLCAnczInKV0pLCBtYXguZWRnZSA9IGMoMC4xLCAwLjIpKQpwbG90KHRveV9tZXNoLCBhc3AgPSAxKQpwb2ludHMoU1BERXRveSRzMSwgU1BERXRveSRzMiwgY29sID0gcmdiKFNQREV0b3kkeSAvIG1heChTUERFdG95JHkpLCAwLCAwLCAwLjUpLCBwY2ggPSAyMCkKYGBgCgpgYGB7ciBzcGRlZml0fQojIFNQREUgcHJvamVjdG9yIG1hdHJpeCBmb3IgZXN0aW1hdGlvbi4KQV9lc3QgPC0gaW5sYS5zcGRlLm1ha2UuQSh0b3lfbWVzaCwgYXMubWF0cml4KFNQREV0b3lbLGMoJ3MxJywgJ3MyJyldKSkKCiMgSW5pdGlhbGl6ZSBleHBvbmVudGlhbCBjb3ZhcmlhbmNlIHN0cnVjdHVyZSBmb3IgU1BERS4Kc3BkZSA8LSBpbmxhLnNwZGUyLm1hdGVybihtZXNoID0gdG95X21lc2gsIGFscGhhID0gMikKCiMgU2V0IHVwIHN0YWNrIGZvciBlc3RpbWF0aW9uLgpzdGFja19pbmRleCA8LSBpbmxhLnNwZGUubWFrZS5pbmRleChuYW1lID0gJ3NwYXRpYWxfZmllbGQnLCBuLnNwZGUgPSBzcGRlJG4uc3BkZSkKc3RhY2tfZXN0IDwtIGlubGEuc3RhY2soZGF0YSA9IGxpc3QoeSA9IFNQREV0b3kkeSksIEEgPSBsaXN0KEFfZXN0KSwgZWZmZWN0cyA9IGxpc3QoYyhzdGFja19pbmRleCwgbGlzdChpbnRlcmNlcHQgPSAxKSkpLCB0YWcgPSAnZXN0JykKCiMgQ3JlYXRlIGEgZ3JpZCBmb3IgcHJlZGljdGlvbi4KdG95X254IDwtIDUwCnRveV9ueSA8LSA1MAp0b3lfZ3JpZCA8LSBleHBhbmQuZ3JpZCh4ID0gc2VxKDAsIDEsIGxlbmd0aC5vdXQgPSB0b3lfbngpLCB5ID0gc2VxKDAsIDEsIGxlbmd0aC5vdXQgPSB0b3lfbnkpKQoKIyBTUERFIHByb2plY3RvciBtYXRyaXggZm9yIHByZWRpY3Rpb24uCkFfcHJlZCA8LSBpbmxhLnNwZGUubWFrZS5BKG1lc2ggPSB0b3lfbWVzaCwgbG9jID0gYXMubWF0cml4KHRveV9ncmlkKSkKCiMgU2V0IHVwIHN0YWNrcyBmb3IgcHJlZGljdGlvbi4Kc3RhY2tfbGF0ZW50IDwtIGlubGEuc3RhY2soZGF0YSA9IGxpc3QoeGkgPSBOQSksIEEgPSBsaXN0KEFfcHJlZCksIGVmZmVjdHMgPSBsaXN0KHN0YWNrX2luZGV4KSwgdGFnID0gJ3ByZWRfbGF0ZW50JykKc3RhY2tfcmVzcG9uc2UgPC0gaW5sYS5zdGFjayhkYXRhID0gbGlzdCh5ID0gTkEpLCBBID0gbGlzdChBX3ByZWQpLCBlZmZlY3RzID0gbGlzdChjKHN0YWNrX2luZGV4LCBsaXN0KGludGVyY2VwdCA9IDEpKSksIHRhZyA9ICdwcmVkX3Jlc3BvbnNlJykKCiMgSm9pbiBhbGwgdGhyZWUgc3RhY2tzLgpzdGFja3MgPC0gaW5sYS5zdGFjayhzdGFja19lc3QsIHN0YWNrX2xhdGVudCwgc3RhY2tfcmVzcG9uc2UpCgojIEZpdCB0aGUgbW9kZWwgd2l0aCBJTkxBLgp0b3lfZml0IDwtIGlubGEoCiAgeSB+IC0xICsgaW50ZXJjZXB0ICsgZihzcGF0aWFsX2ZpZWxkLCBtb2RlbCA9IHNwZGUpLAogIGRhdGEgPSBpbmxhLnN0YWNrLmRhdGEoc3RhY2tzKSwKICBjb250cm9sLnByZWRpY3RvciA9IGxpc3QoQSA9IGlubGEuc3RhY2suQShzdGFja3MpLCBjb21wdXRlID0gVFJVRSkKKQoKIyBPdXRwdXQgcG9zdGVyaW9yIHN1bW1hcmllcy4KdG95X2ZpdCRzdW1tYXJ5LmZpeGVkCnRveV9maXQkc3VtbWFyeS5oeXBlcnBhcgoKIyBFeHRyYWN0IHBvc3RlcmlvciBtZWFuIG9mIGxhdGVudCBzcGF0aWFsIGZpZWxkLgppbmRleF9sYXRlbnQgPC0gaW5sYS5zdGFjay5pbmRleChzdGFja3MsIHRhZyA9ICdwcmVkX2xhdGVudCcpJGRhdGEKcG9zdF9tZWFuIDwtIHRveV9maXQkc3VtbWFyeS5saW5lYXIucHJlZGljdG9yW2luZGV4X2xhdGVudCwgJ21lYW4nXQpwb3N0X3NkIDwtIHRveV9maXQkc3VtbWFyeS5saW5lYXIucHJlZGljdG9yW2luZGV4X2xhdGVudCwgJ3NkJ10KCiMgUGxvdCB0aGUgcG9zdGVyaW9yIG1lYW4gYW5kIFNEIG9mIHRoZSBsYXRlbnQgc3BhdGlhbCBmaWVsZC4KcGxvdChpbShtYXRyaXgocG9zdF9tZWFuLCBucm93ID0gdG95X254LCBuY29sID0gdG95X255KSwgeHJhbmdlID0gcmFuZ2UodG95X2dyaWQkeCksIHlyYW5nZSA9IHJhbmdlKHRveV9ncmlkJHkpKSwgbWFpbiA9ICdQb3N0ZXJpb3IgTWVhbiBvZiBTcGF0aWFsIEZpZWxkJykKcG9pbnRzKFNQREV0b3kkczEsIFNQREV0b3kkczIsIGNvbCA9IHJnYihTUERFdG95JHkgLyBtYXgoU1BERXRveSR5KSwgMCwgMCwgMC41KSwgcGNoID0gMjApCnBsb3QoaW0obWF0cml4KHBvc3Rfc2QsIG5yb3cgPSB0b3lfbngsIG5jb2wgPSB0b3lfbnkpLCB4cmFuZ2UgPSByYW5nZSh0b3lfZ3JpZCR4KSwgeXJhbmdlID0gcmFuZ2UodG95X2dyaWQkeSkpLCBtYWluID0gJ1Bvc3RlcmlvciBTRCBvZiBTcGF0aWFsIEZpZWxkJykKcG9pbnRzKFNQREV0b3kkczEsIFNQREV0b3kkczIsIGNvbCA9IHJnYihTUERFdG95JHkgLyBtYXgoU1BERXRveSR5KSwgMCwgMCwgMC41KSwgcGNoID0gMjApCmBgYAoKCiMgQmVpIERhdGFzZXQgYW5kIGBpbmxhYnJ1YAoKRXhhbXBsZSBmcm9tIEBtb2VsbGVyd2FhZ2VwZXRlcnNlbiwgX0JlaWxzY2htaWVkaWEgcGVuZHVsYSBMYXVyYWNlYWVfIGxvY2F0aW9ucwppbiBhIHBsb3QgaW4gUGFuYW1hLiBgYmVpYCBkYXRhc2V0IGluIGBzcGF0c3RhdGAgW0BzcGF0c3RhdF0uCgpgYGB7ciBiZWlwdHN9CiMgUGxvdCB0aGUgZnVsbCBwb2ludCBwYXR0ZXJuLgpwbG90KGJlaSwgcGNoID0gJy4nLCBjb2xzID0gJ2JsYWNrJywgbWFpbiA9ICdSZWFsaXplZCBQb2ludCBQYXR0ZXJuJykKYGBgCgpgYGB7ciBiZWltZXNofQpiZWlfY29ybmVycyA8LSB2ZXJ0aWNlcy5vd2luKFdpbmRvdyhiZWkpKQpiZWlfZG9tYWluIDwtIGNiaW5kKGJlaV9jb3JuZXJzJHgsIGJlaV9jb3JuZXJzJHkpCmJlaV9mdWxsX21lc2ggPC0gaW5sYS5tZXNoLjJkKGNiaW5kKGJlaSR4LCBiZWkkeSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGN1dG9mZiA9IDUwLCBtYXguZWRnZSA9IGMoNTAsIDEwMCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxvYy5kb21haW4gPSBiZWlfZG9tYWluKQpwbG90KGJlaV9mdWxsX21lc2gsIGFzcCA9IDEpCnBsb3QoV2luZG93KGJlaSksIGJvcmRlciA9ICdibHVlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaSwgcGNoID0gJy4nLCBjb2wgPSAnYmx1ZScpCmBgYAoKYGBge3IgYmVpZnVsbGxnY3AsIGNhY2hlID0gVFJVRX0KYmVpX2Z1bGxfc3BkZiA8LSBhcy5TcGF0aWFsUG9pbnRzLnBwcChiZWkpCiMgQ0hFQ0sgUFJJT1JTIQptYXRlcm5fZnVsbCA8LSBpbmxhLnNwZGUyLnBjbWF0ZXJuKGJlaV9mdWxsX21lc2gsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3Iuc2lnbWEgPSBjKDAuMSwgMC45OSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3IucmFuZ2UgPSBjKDUsIDAuMDEpKQpjbXBfZnVsbCA8LSBjb29yZGluYXRlcyB+IG15U21vb3RoKG1hcCA9IGNvb3JkaW5hdGVzLCBtb2RlbCA9IG1hdGVybl9mdWxsKSArIEludGVyY2VwdApiZWlfZnVsbF9sZ2NwIDwtIGxnY3AoY21wX2Z1bGwsIGJlaV9mdWxsX3NwZGYpCmxhbWJkYV9mdWxsIDwtIHByZWRpY3QoYmVpX2Z1bGxfbGdjcCwgcGl4ZWxzKGJlaV9mdWxsX21lc2gpLCB+IGV4cChteVNtb290aCArIEludGVyY2VwdCkpCgojIFBsb3QgcG9zdGVyaW9yIG1lYW5zIGFuZCBwb3N0ZXJpb3Igc2QuCnBsb3QobGFtYmRhX2Z1bGwpCnBsb3QoV2luZG93KGJlaSksIGJvcmRlciA9ICd3aGl0ZScsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWksIHBjaCA9ICcuJywgY29sID0gJ3doaXRlJykKcGxvdChsYW1iZGFfZnVsbFsnc2QnXSkKcGxvdChXaW5kb3coYmVpKSwgYm9yZGVyID0gJ3doaXRlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaSwgcGNoID0gJy4nLCBjb2wgPSAnd2hpdGUnKQpgYGAKCmBgYHtyIGJlaWhvbGV9CiMgVGFrZSBhIHNhbXBsZSBvZiBxdWFkcmF0cyBhbmQgcGxvdCB0aGUgb2JzZXJ2ZWQgcG9pbnQgcGF0dGVybi4Kc2V0LnNlZWQoODQzMjMpCm5fcXVhZHMgPC0gMTAKYm90bGVmdCA8LSBjYmluZChydW5pZihuX3F1YWRzLCAwLCA5NTApLCBydW5pZihuX3F1YWRzLCAwLCA0NTApKQpiZWlfaW50ZXJpb3IgPC0gbGFwcGx5KHNlcV9sZW4obnJvdyhib3RsZWZ0KSksIGZ1bmN0aW9uKHIpe3JldHVybigKICAgIGNiaW5kKAogICAgICBib3RsZWZ0W3IsIDFdICsgYygwLCAwLCA1MCwgNTApLAogICAgICBib3RsZWZ0W3IsIDJdICsgYygwLCA1MCwgNTAsIDApCiAgICApCiAgKX0pCmJlaV93aW4gPC0gZG8uY2FsbCgKICB1bmlvbi5vd2luLAogIGFwcGx5KGJvdGxlZnQsIDEsIGZ1bmN0aW9uKHgpe3JldHVybigKICAgIG93aW4oeFsxXSArIGMoMCwgNTApLCB4WzJdICsgYygwLCA1MCkpCiAgKX0pCikKYmVpX2hvbGUgPC0gYmVpW2NvbXBsZW1lbnQub3dpbihiZWlfd2luKV0KYmVpX3NhbXAgPC0gYmVpW2JlaV93aW5dCmJlaV93aW5kb3dfZnVsbCA8LSBXaW5kb3coYmVpKQoKcGxvdChiZWlfaG9sZSwgbWFpbiA9ICdPYnNlcnZlZCBTdWJyZWdpb24nLCBwY2ggPSAnLicsIGNvbHMgPSAnYmxhY2snKQpgYGAKCmBgYHtyIGJlaWhvbGVtZXNofQpiZWlfaG9sZV9tZXNoIDwtIGlubGEubWVzaC4yZChjYmluZChiZWlfaG9sZSR4LCBiZWlfaG9sZSR5KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY3V0b2ZmID0gNTAsIG1heC5lZGdlID0gYyg1MCwgMTAwKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbG9jLmRvbWFpbiA9IGJlaV9kb21haW4pCnBsb3QoYmVpX2hvbGVfbWVzaCwgYXNwID0gMSkKcGxvdChXaW5kb3coYmVpKSwgYm9yZGVyID0gJ2JsdWUnLCBhZGQgPSBUUlVFKQpwb2ludHMoYmVpX2hvbGUsIHBjaCA9ICcuJywgY29sID0gJ2JsdWUnKQpgYGAKCmBgYHtyIGJlaWhvbGVsZ2NwLCBjYWNoZSA9IFRSVUV9CmJlaV9ob2xlX3NwZGYgPC0gYXMuU3BhdGlhbFBvaW50cy5wcHAoYmVpX2hvbGUpCiMgQ0hFQ0sgUFJJT1JTIQptYXRlcm5faG9sZSA8LSBpbmxhLnNwZGUyLnBjbWF0ZXJuKGJlaV9ob2xlX21lc2gsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3Iuc2lnbWEgPSBjKDAuMSwgMC45OSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3IucmFuZ2UgPSBjKDUsIDAuMDEpKQpjbXBfaG9sZSA8LSBjb29yZGluYXRlcyB+IG15U21vb3RoKG1hcCA9IGNvb3JkaW5hdGVzLCBtb2RlbCA9IG1hdGVybl9ob2xlKSArIEludGVyY2VwdApiZWlfaG9sZV9sZ2NwIDwtIGxnY3AoY21wX2hvbGUsIGJlaV9ob2xlX3NwZGYpCmxhbWJkYV9ob2xlIDwtIHByZWRpY3QoYmVpX2hvbGVfbGdjcCwgcGl4ZWxzKGJlaV9ob2xlX21lc2gpLCB+IGV4cChteVNtb290aCArIEludGVyY2VwdCkpCgojIFBsb3QgcG9zdGVyaW9yIG1lYW5zIGFuZCBwb3N0ZXJpb3Igc2QuCnBsb3QobGFtYmRhX2hvbGUpCnBsb3QoV2luZG93KGJlaV9ob2xlKSwgYm9yZGVyID0gJ3doaXRlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaV9ob2xlLCBwY2ggPSAnLicsIGNvbCA9ICd3aGl0ZScpCnBsb3QobGFtYmRhX2hvbGVbJ3NkJ10pCnBsb3QoV2luZG93KGJlaV9ob2xlKSwgYm9yZGVyID0gJ3doaXRlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaV9ob2xlLCBwY2ggPSAnLicsIGNvbCA9ICd3aGl0ZScpCmBgYAoKYGBge3IgYmVpc2FtcH0KcGxvdChiZWlfd2luZG93X2Z1bGwsIG1haW4gPSAnT2JzZXJ2ZWQgU2FtcGxlJykKcGxvdChiZWlfd2luLCBhZGQgPSBUUlVFKQpwbG90KGJlaV9zYW1wLCBwY2ggPSAnLicsIGNvbHMgPSAnYmxhY2snLCBhZGQgPSBUUlVFKQpgYGAKCmBgYHtyIGJlaXNhbXBtZXNofQpiZWlfc2FtcF9tZXNoIDwtIGlubGEubWVzaC4yZChjYmluZChiZWlfc2FtcCR4LCBiZWlfc2FtcCR5KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY3V0b2ZmID0gNTAsIG1heC5lZGdlID0gYyg1MCwgMTAwKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbG9jLmRvbWFpbiA9IGJlaV9kb21haW4pCnBsb3QoYmVpX3NhbXBfbWVzaCwgYXNwID0gMSkKcGxvdChXaW5kb3coYmVpKSwgYm9yZGVyID0gJ2JsdWUnLCBhZGQgPSBUUlVFKQpwbG90KFdpbmRvdyhiZWlfc2FtcCksIGJvcmRlciA9ICdibHVlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaV9zYW1wLCBwY2ggPSAnLicsIGNvbCA9ICdibHVlJykKYGBgCgpgYGB7ciBiZWlzYW1wbGdjcCwgY2FjaGUgPSBUUlVFfQpiZWlfc2FtcF9zcGRmIDwtIGFzLlNwYXRpYWxQb2ludHMucHBwKGJlaV9zYW1wKQojIENIRUNLIFBSSU9SUyEKbWF0ZXJuX3NhbXAgPC0gaW5sYS5zcGRlMi5wY21hdGVybihiZWlfc2FtcF9tZXNoLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW9yLnNpZ21hID0gYygwLjEsIDAuOTkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW9yLnJhbmdlID0gYyg1LCAwLjAxKSkKY21wX3NhbXAgPC0gY29vcmRpbmF0ZXMgfiBteVNtb290aChtYXAgPSBjb29yZGluYXRlcywgbW9kZWwgPSBtYXRlcm5fc2FtcCkgKyBJbnRlcmNlcHQKYmVpX3NhbXBfbGdjcCA8LSBsZ2NwKGNtcF9zYW1wLCBiZWlfc2FtcF9zcGRmKQpsYW1iZGFfc2FtcCA8LSBwcmVkaWN0KGJlaV9zYW1wX2xnY3AsIHBpeGVscyhiZWlfc2FtcF9tZXNoKSwgfiBleHAobXlTbW9vdGggKyBJbnRlcmNlcHQpKQoKIyBQbG90IHBvc3RlcmlvciBtZWFucyBhbmQgcG9zdGVyaW9yIHNkLgpwbG90KGxhbWJkYV9zYW1wKQpwbG90KFdpbmRvdyhiZWkpLCBib3JkZXIgPSAnd2hpdGUnLCBhZGQgPSBUUlVFKQpwbG90KFdpbmRvdyhiZWlfc2FtcCksIGJvcmRlciA9ICd3aGl0ZScsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWlfc2FtcCwgcGNoID0gJy4nLCBjb2wgPSAnd2hpdGUnKQpwbG90KGxhbWJkYV9zYW1wWydzZCddKQpwbG90KFdpbmRvdyhiZWkpLCBib3JkZXIgPSAnd2hpdGUnLCBhZGQgPSBUUlVFKQpwbG90KFdpbmRvdyhiZWlfc2FtcCksIGJvcmRlciA9ICd3aGl0ZScsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWlfc2FtcCwgcGNoID0gJy4nLCBjb2wgPSAnd2hpdGUnKQpgYGAKCiMgQmVpIERhdGFzZXQgd2l0aG91dCBgaW5sYWJydWAKCmBgYHtyIGJlaWlubGEsIGNhY2hlID0gVFJVRX0KY2VudGVycyA8LSBncmlkY2VudGVycyhkaWxhdGlvbihiZWlfd2luZG93X2Z1bGwsIDQwKSwgNDAsIDIwKQpkeCA8LSBzdW0odW5pcXVlKGNlbnRlcnMkeClbMToyXSAqIGMoLTEsIDEpKSAvIDIKZHkgPC0gc3VtKHVuaXF1ZShjZW50ZXJzJHkpWzE6Ml0gKiBjKC0xLCAxKSkgLyAyCmJlaV9kZiA8LSBkYXRhLmZyYW1lKHggPSBjZW50ZXJzJHgsIHkgPSBjZW50ZXJzJHksCiAgICAgICAgICAgICAgICAgICAgIGNvdW50ID0gTkFfaW50ZWdlcl8sIGFyZWEgPSBOQV9yZWFsXykKCmZvcihyIGluIHNlcV9sZW4obnJvdyhiZWlfZGYpKSl7CiAgYmVpX2RmJGNvdW50W3JdIDwtIHN1bShiZWkkeCA+PSBiZWlfZGYkeFtyXSAtIGR4ICYKICAgICAgICAgICAgICAgICAgICAgICAgIGJlaSR4IDwgYmVpX2RmJHhbcl0gKyBkeCAmCiAgICAgICAgICAgICAgICAgICAgICAgICBiZWkkeSA+PSBiZWlfZGYkeVtyXSAtIGR5ICYKICAgICAgICAgICAgICAgICAgICAgICAgIGJlaSR5IDwgYmVpX2RmJHlbcl0gKyBkeSkKICBiZWlfZGYkYXJlYVtyXSA8LSBhcmVhKFdpbmRvdyhiZWkpW293aW4oYyhiZWlfZGYkeFtyXSAtIGR4LCBiZWlfZGYkeFtyXSArIGR4KSwgYyhiZWlfZGYkeVtyXSAtIGR5LCBiZWlfZGYkeVtyXSArIGR5KSldKQp9CgpwYXIobWFyID0gYygwLjUsIDAsIDIsIDIpKQpwbG90KGltKHQobWF0cml4KGJlaV9kZiRjb3VudCwgbnJvdyA9IGxlbmd0aCh1bmlxdWUoYmVpX2RmJHgpKSkpLCB1bmlxdWUoYmVpX2RmJHgpLCB1bmlxdWUoYmVpX2RmJHkpLCB1bml0bmFtZSA9ICdtZXRlcnMnKSwgbmNvbGNvdXJzID0gcmFuZ2UoYmVpX2RmJGNvdW50KSAlKiUgYygtMSwgMSkgKyAxLCBtYWluID0gJ0Jpbm5lZCBUcmVlIENvdW50cycpCnBsb3QoYmVpX3dpbmRvd19mdWxsLCBib3JkZXIgPSAnd2hpdGUnLCBhZGQgPSBUUlVFKQpwb2ludHMoYmVpLCBwY2ggPSAnLicsIGNvbCA9ICdibGFjaycpCgojIFNQREUgcHJvamVjdG9yIG1hdHJpeCBmb3IgZXN0aW1hdGlvbi4KZnVsbF9BX2VzdCA8LSBpbmxhLnNwZGUubWFrZS5BKGJlaV9mdWxsX21lc2gsIGFzLm1hdHJpeChiZWlfZGZbYmVpX2RmJGFyZWEgPiAwLCBjKCd4JywgJ3knKV0pKQoKIyBJbml0aWFsaXplIGV4cG9uZW50aWFsIGNvdmFyaWFuY2Ugc3RydWN0dXJlIGZvciBTUERFLgpmdWxsX3NwZGUgPC0gaW5sYS5zcGRlMi5tYXRlcm4obWVzaCA9IGJlaV9mdWxsX21lc2gsIGFscGhhID0gMikKCiMgU2V0IHVwIHN0YWNrIGZvciBlc3RpbWF0aW9uLgpzdGFja19pbmRleCA8LSBpbmxhLnNwZGUubWFrZS5pbmRleChuYW1lID0gJ3NwYXRpYWxfZmllbGQnLCBuLnNwZGUgPSBmdWxsX3NwZGUkbi5zcGRlKQpzdGFja19lc3QgPC0gaW5sYS5zdGFjayhkYXRhID0gbGlzdChjb3VudCA9IGJlaV9kZiRjb3VudFtiZWlfZGYkYXJlYSA+IDBdLCBsYXJlYSA9IGxvZyhiZWlfZGYkYXJlYVtiZWlfZGYkYXJlYSA+IDBdKSksIEEgPSBsaXN0KGZ1bGxfQV9lc3QpLCBlZmZlY3RzID0gbGlzdChjKHN0YWNrX2luZGV4LCBsaXN0KGludGVyY2VwdCA9IDEpKSksIHRhZyA9ICdlc3QnKQoKIyBTUERFIHByb2plY3RvciBtYXRyaXggZm9yIHByZWRpY3Rpb24uCmZ1bGxfQV9wcmVkIDwtIGlubGEuc3BkZS5tYWtlLkEobWVzaCA9IGJlaV9mdWxsX21lc2gsIGxvYyA9IGFzLm1hdHJpeChiZWlfZGZbLGMoJ3gnLCAneScpXSkpCgojIFNldCB1cCBzdGFja3MgZm9yIHByZWRpY3Rpb24uCnN0YWNrX2xhdGVudCA8LSBpbmxhLnN0YWNrKGRhdGEgPSBsaXN0KHhpID0gTkEpLCBBID0gbGlzdChmdWxsX0FfcHJlZCksIGVmZmVjdHMgPSBsaXN0KHN0YWNrX2luZGV4KSwgdGFnID0gJ3ByZWRfbGF0ZW50JykKc3RhY2tfcmVzcG9uc2UgPC0gaW5sYS5zdGFjayhkYXRhID0gbGlzdChjb3VudCA9IE5BKSwgQSA9IGxpc3QoZnVsbF9BX3ByZWQpLCBlZmZlY3RzID0gbGlzdChjKHN0YWNrX2luZGV4LCBsaXN0KGludGVyY2VwdCA9IDEpKSksIHRhZyA9ICdwcmVkX3Jlc3BvbnNlJykKCiMgSm9pbiBhbGwgdGhyZWUgc3RhY2tzLgpzdGFja3MgPC0gaW5sYS5zdGFjayhzdGFja19lc3QsIHN0YWNrX2xhdGVudCwgc3RhY2tfcmVzcG9uc2UpCgojIEZpdCB0aGUgbW9kZWwgd2l0aCBJTkxBLgpiZWlfZnVsbF9maXQgPC0gaW5sYSgKICBjb3VudCB+IC0xICsgaW50ZXJjZXB0ICsgZihzcGF0aWFsX2ZpZWxkLCBtb2RlbCA9IGZ1bGxfc3BkZSksCiAgb2Zmc2V0ID0gbGFyZWEsIGZhbWlseSA9ICdwb2lzc29uJywKICBkYXRhID0gaW5sYS5zdGFjay5kYXRhKHN0YWNrcyksCiAgY29udHJvbC5wcmVkaWN0b3IgPSBsaXN0KEEgPSBpbmxhLnN0YWNrLkEoc3RhY2tzKSwgY29tcHV0ZSA9IFRSVUUpCikKCiMgT3V0cHV0IHBvc3RlcmlvciBzdW1tYXJpZXMuCmJlaV9mdWxsX2ZpdCRzdW1tYXJ5LmZpeGVkCmJlaV9mdWxsX2ZpdCRzdW1tYXJ5Lmh5cGVycGFyCgojIEV4dHJhY3QgcG9zdGVyaW9yIG1lYW4gb2YgbGF0ZW50IHNwYXRpYWwgZmllbGQuCmluZGV4X3ByZWQgPC0gaW5sYS5zdGFjay5pbmRleChzdGFja3MsIHRhZyA9ICdwcmVkX2xhdGVudCcpJGRhdGEKcG9zdF9tZWFuIDwtIGJlaV9mdWxsX2ZpdCRzdW1tYXJ5LmxpbmVhci5wcmVkaWN0b3JbaW5kZXhfcHJlZCwgJ21lYW4nXQpwb3N0X3NkIDwtIGJlaV9mdWxsX2ZpdCRzdW1tYXJ5LmxpbmVhci5wcmVkaWN0b3JbaW5kZXhfcHJlZCwgJ3NkJ10KCiMgUGxvdCB0aGUgcG9zdGVyaW9yIG1lYW4gYW5kIFNEIG9mIHRoZSBsYXRlbnQgc3BhdGlhbCBmaWVsZC4KcGxvdChpbSh0KG1hdHJpeChwb3N0X21lYW4sIG5yb3cgPSBsZW5ndGgodW5pcXVlKGNlbnRlcnMkeCkpLCBuY29sID0gbGVuZ3RoKHVuaXF1ZShjZW50ZXJzJHkpKSkpLCB1bmlxdWUoY2VudGVycyR4KSwgdW5pcXVlKGNlbnRlcnMkeSkpLCBtYWluID0gJ1Bvc3RlcmlvciBNZWFuIG9mIFNwYXRpYWwgRmllbGQnKQpwbG90KGJlaV93aW5kb3dfZnVsbCwgYWRkID0gVFJVRSkKcG9pbnRzKGJlaSwgcGNoID0gJy4nLCBjb2wgPSAnYmxhY2snKQpwbG90KGltKHQobWF0cml4KHBvc3Rfc2QsIG5yb3cgPSBsZW5ndGgodW5pcXVlKGNlbnRlcnMkeCkpLCBuY29sID0gbGVuZ3RoKHVuaXF1ZShjZW50ZXJzJHkpKSkpLCB1bmlxdWUoY2VudGVycyR4KSwgdW5pcXVlKGNlbnRlcnMkeSkpLCBtYWluID0gJ1Bvc3RlcmlvciBTRCBvZiBTcGF0aWFsIEZpZWxkJykKcGxvdChiZWlfd2luZG93X2Z1bGwsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWksIHBjaCA9ICcuJywgY29sID0gJ2JsYWNrJykKYGBgCgpgYGB7ciBiZWlob2xlaW5sYX0KYmVpaG9sZV9kZiA8LSBkYXRhLmZyYW1lKHggPSBjZW50ZXJzJHgsIHkgPSBjZW50ZXJzJHksCiAgICAgICAgICAgICAgICAgICAgICAgICBjb3VudCA9IE5BX2ludGVnZXJfLCBhcmVhID0gTkFfcmVhbF8pCgpmb3IociBpbiBzZXFfbGVuKG5yb3coYmVpaG9sZV9kZikpKXsKICBiZWlob2xlX2RmJGNvdW50W3JdIDwtIHN1bShiZWlfaG9sZSR4ID49IGJlaWhvbGVfZGYkeFtyXSAtIGR4ICYKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBiZWlfaG9sZSR4IDwgYmVpaG9sZV9kZiR4W3JdICsgZHggJgogICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJlaV9ob2xlJHkgPj0gYmVpaG9sZV9kZiR5W3JdIC0gZHkgJgogICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJlaV9ob2xlJHkgPCBiZWlob2xlX2RmJHlbcl0gKyBkeSkKICBiZWlob2xlX2RmJGFyZWFbcl0gPC0gYXJlYShXaW5kb3coYmVpX2hvbGUpW293aW4oYyhiZWlob2xlX2RmJHhbcl0gLSBkeCwgYmVpaG9sZV9kZiR4W3JdICsgZHgpLCBjKGJlaWhvbGVfZGYkeVtyXSAtIGR5LCBiZWlob2xlX2RmJHlbcl0gKyBkeSkpXSkKfQoKcGFyKG1hciA9IGMoMC41LCAwLCAyLCAyKSkKcGxvdChpbSh0KG1hdHJpeChiZWlob2xlX2RmJGNvdW50LCBucm93ID0gbGVuZ3RoKHVuaXF1ZShiZWlob2xlX2RmJHgpKSkpLCB1bmlxdWUoYmVpaG9sZV9kZiR4KSwgdW5pcXVlKGJlaWhvbGVfZGYkeSksIHVuaXRuYW1lID0gJ21ldGVycycpLCBuY29sY291cnMgPSByYW5nZShiZWlob2xlX2RmJGNvdW50KSAlKiUgYygtMSwgMSkgKyAxLCBtYWluID0gJ0Jpbm5lZCBUcmVlIENvdW50cycpCnBsb3QoV2luZG93KGJlaV9ob2xlKSwgYm9yZGVyID0gJ3doaXRlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaSwgcGNoID0gJy4nLCBjb2wgPSAnIzAwMDAwMDQwJykKYGBgCgoKIyBSZWZlcmVuY2VzCgo=